package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/number-of-ways-to-select-buildings/description/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/11/4 19:17
 * @since JDK17
 */

public class Solution35 {
    public long numberOfWays(String s) {
        long ans = 0, z = 0, o = 0, l0 = 0, l1 = 0;
        char[] arr = s.toCharArray();
        // 0的数量
        int n = arr.length;
        for (char x : arr) {
            z += x == '0' ? 1 : 0;
        }
        for (int i = 0; i < n; i++) {
            var x = arr[i];
            if (x == '1') {
                ans += l0 * (z - l0);
            } else {
                l1 = i - l0;    // 左边1的数量
                ans += l1 * (n - z - l1);
                l0++;
            }
        }

        return ans;
    }
}
